//1446.连续字符

//给你一个字符串 s ，字符串的「能量」定义为：只包含一种字符的最长非空子字符串的长度。
//请你返回字符串 s 的 能量。

//class Solution {
//public:
//    int maxPower(string s) {
//        int ans = 1, tmp = 1, n = s.size();
//        for (int i = 1; i < n; i++) {
//            while (s[i - 1] == s[i]) {
//                i++;
//                tmp++;
//            }
//            ans = max(ans, tmp);
//            tmp = 1;
//        }
//        return ans;
//    }
//};

//1869.哪种连续子字符串更长

//给你一个二进制字符串 s 。如果字符串中由 1 组成的 最长 连续子字符串 严格长于 由 0 组成的 最长 连续子字符串，返回 true ；否则，返回 false 。
//例如，s = "110100010" 中，由 1 组成的最长连续子字符串的长度是 2 ，由 0 组成的最长连续子字符串的长度是 3 。
//注意，如果字符串中不存在 0 ，此时认为由 0 组成的最长连续子字符串的长度是 0 。字符串中不存在 1 的情况也适用此规则。

//class Solution {
//public:
//    bool checkZeroOnes(string s) {
//        int max0 = 0, max1 = 0, n = s.size();
//        for (int i = 0; i < n; i++) {
//            int t = i;
//            while (s[i] == s[i + 1]) {
//                i++;
//            }
//            if (s[i] == '1') {
//                max1 = max(max1, i - t + 1);
//            }
//            else {
//                max0 = max(max0, i - t + 1);
//            }
//        }
//        return max1 > max0;
//    }
//};

//2414.最长的字母序连续子字符串的长度

//字母序连续字符串 是由字母表中连续字母组成的字符串。换句话说，字符串 "abcdefghijklmnopqrstuvwxyz" 的任意子字符串都是 字母序连续字符串 。
//例如，"abc" 是一个字母序连续字符串，而 "acb" 和 "za" 不是。
//给你一个仅由小写英文字母组成的字符串 s ，返回其 最长 的 字母序连续子字符串 的长度。

//class Solution {
//public:
//    int longestContinuousSubstring(string s) {
//        int ans = 1, n = s.size(), cnt = 1;
//        for (int i = 1; i < n; i++) {
//            if (s[i - 1] + 1 == s[i]) {
//                cnt++;
//            }
//            else {
//                ans = max(ans, cnt);
//                cnt = 1;
//            }
//        }
//        ans = max(ans, cnt);
//        return ans;
//    }
//};

//3456.找出长度为 K 的特殊子字符串

//给你一个字符串 s 和一个整数 k。
//判断是否存在一个长度 恰好 为 k 的子字符串，该子字符串需要满足以下条件：
//该子字符串 只包含一个唯一字符（例如，"aaa" 或 "bbb"）。
//如果该子字符串的 前面 有字符，则该字符必须与子字符串中的字符不同。
//如果该子字符串的 后面 有字符，则该字符也必须与子字符串中的字符不同。
//如果存在这样的子串，返回 true；否则，返回 false。
//子字符串 是字符串中的连续、非空字符序列。

//class Solution {
//public:
//    bool hasSpecialSubstring(string s, int k) {
//        int n = s.size(), index;
//        for (int i = 0; i < n; i++) {
//            index = i;
//            while (i < n - 1 && s[i] == s[i + 1]) {
//                i++;
//            }
//            if (i - index + 1 == k) {
//                return true;
//            }
//        }
//        return false;
//    }
//};

//1957.删除字符使字符串变好

//一个字符串如果没有 三个连续 相同字符，那么它就是一个 好字符串 。
//给你一个字符串 s ，请你从 s 删除 最少 的字符，使它变成一个 好字符串 。
//请你返回删除后的字符串。题目数据保证答案总是 唯一的 。

//class Solution {
//public:
//    string makeFancyString(string s) {
//        string ans;
//        int cnt{}, n = s.size();
//        for (int i{}; i < n; i++) {
//            cnt++;
//            if (cnt < 3) {
//                ans += s[i];
//            }
//            if (i < n - 1 && s[i] != s[i + 1]) {
//                cnt = 0;
//            }
//        }
//
//        return ans;
//    }
//};

//674.最长连续递增序列

//给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
//连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，
//都有 nums[i] < nums[i + 1] ，那么子序列[nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

//class Solution {
//public:
//    int findLengthOfLCIS(vector<int>& nums) {
//        int n = nums.size(), ans = 1, index;
//        for (int i = 0; i < n; i++) {
//            index = i;
//            while (i < n - 1 && nums[i] < nums[i + 1]) {
//                i++;
//            }
//            ans = max(ans, i - index + 1);
//        }
//        return ans;
//    }
//};

//978.最长湍流子数组

//给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。
//如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。
//更正式地来说，当 arr 的子数组 A[i], A[i + 1], ..., A[j] 满足仅满足下列条件时，我们称其为湍流子数组：
//若 i <= k < j ：当 k 为奇数时， A[k] > A[k + 1]，且当 k 为偶数时，A[k] < A[k + 1]；
//或 若 i <= k < j ：当 k 为偶数时，A[k] > A[k + 1] ，且当 k 为奇数时， A[k] < A[k + 1]。

//class Solution {
//public:
//    int maxTurbulenceSize(vector<int>& arr) {
//        int n = arr.size();
//        int ans = 1, i = 0, index;
//        while (i < n - 1) {
//            if (arr[i + 1] == arr[i]) {
//                i++;
//                continue;
//            }
//            index = i;
//            i++;
//            while (i < n - 1 &&
//                (long long)(arr[i + 1] - arr[i]) * (arr[i] - arr[i - 1]) <
//                0) {
//                i++;
//            }
//            ans = max(ans, i - index + 1);
//        }
//        return ans;
//    }
//};

//2110.股票平滑下跌阶段的数目

//给你一个整数数组 prices ，表示一支股票的历史每日股价，其中 prices[i] 是这支股票第 i 天的价格。
//一个 平滑下降的阶段 定义为：对于 连续一天或者多天 ，每日股价都比 前一日股价恰好少 1 ，这个阶段第一天的股价没有限制。
//请你返回 平滑下降阶段 的数目。

//class Solution {
//public:
//    long long getDescentPeriods(vector<int>& prices) {
//        int n = prices.size(), i = 0, index;
//        long long ans = 0;
//        while (i < n) {
//            index = i;
//            i++;
//            while (i < n && prices[i - 1] - 1 == prices[i]) {
//                ans += i - index;
//                i++;
//            }
//            ans += i - index;
//        }
//        return ans;
//    }
//};

//228.汇总区间

//给定一个  无重复元素 的 有序 整数数组 nums 。
//区间[a, b] 是从 a 到 b（包含）的所有整数的集合。
//返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个区间但不属于 nums 的数字 x 。
//列表中的每个区间范围[a, b] 应该按如下格式输出：
//"a->b" ，如果 a != b
//"a" ，如果 a == b

//class Solution {
//public:
//    vector<string> summaryRanges(vector<int>& nums) {
//        int n = nums.size(), i = 0, index;
//        vector<string> ans;
//        while (i < n) {
//            index = i;
//            i++;
//            while (i < n && nums[i - 1] + 1 == nums[i]) {
//                i++;
//            }
//            string tmp = to_string(nums[index]);
//            if (index < i - 1) {
//                tmp += "->" + to_string(nums[i - 1]);//(+=) == (.append()) > (+),+= +换成两个+=更好
//            }
//            ans.emplace_back(tmp);
//        }
//        return ans;
//    }
//};

//2760.最长奇偶子数组

//给你一个下标从 0 开始的整数数组 nums 和一个整数 threshold 。
//请你从 nums 的子数组中找出以下标 l 开头、下标 r 结尾(0 <= l <= r < nums.length) 且满足以下条件的 最长子数组 ：
//nums[l] % 2 == 0
//对于范围[l, r - 1] 内的所有下标 i ，nums[i] % 2 != nums[i + 1] % 2
//对于范围[l, r] 内的所有下标 i ，nums[i] <= threshold
//以整数形式返回满足题目要求的最长子数组的长度。
//注意：子数组 是数组中的一个连续非空元素序列。

//class Solution {
//public:
//    int longestAlternatingSubarray(vector<int>& nums, int threshold) {
//        int n = nums.size(), ans = 0, i = 0, index;
//        while (i < n) {
//            if (nums[i] > threshold || nums[i] % 2) {
//                i++;
//                continue;
//            }
//            index = i;
//            i++;
//            while (i < n && nums[i] <= threshold && nums[i] % 2 != nums[i - 1] % 2) {
//                i++;
//            }
//            ans = max(ans, i - index);
//        }
//        return ans;
//    }
//};

//1887.使数组元素相等的减少操作次数

//给你一个整数数组 nums ，你的目标是令 nums 中的所有元素相等。完成一次减少操作需要遵照下面的几个步骤：
//找出 nums 中的 最大 值。记这个值为 largest 并取其下标 i （下标从 0 开始计数）。如果有多个元素都是最大值，则取最小的 i 。
//找出 nums 中的 下一个最大 值，这个值 严格小于 largest ，记为 nextLargest 。
//将 nums[i] 减少到 nextLargest 。
//返回使 nums 中的所有元素相等的操作次数。

//class Solution {
//public:
//    int reductionOperations(vector<int>& nums) {
//        ranges::sort(nums);
//        int i = 0, n = nums.size(), ans = 0, cnt = 0, index;
//        while (i < n) {
//            index = i;
//            i++;
//            while (i < n && nums[i] == nums[index]) {
//                i++;
//            }
//            ans += (i - index) * cnt++;
//        }
//        return ans;
//    }
//};

//845.数组中的最长山脉

//把符合下列属性的数组 arr 称为 山脉数组 ：
//arr.length >= 3
//存在下标 i（0 < i < arr.length - 1），满足arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
//arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
//给出一个整数数组 arr，返回最长山脉子数组的长度。如果不存在山脉子数组，返回 0 。

//class Solution {
//public:
//    int longestMountain(vector<int>& arr) {
//        int n = arr.size();
//        if (n < 3) {
//            return 0;
//        }
//        vector<int> left(n);
//        for (int i = 1; i < n; ++i) {
//            left[i] = (arr[i - 1] < arr[i] ? left[i - 1] + 1 : 0);
//        }
//        vector<int> right(n);
//        for (int i = n - 2; i >= 0; --i) {
//            right[i] = (arr[i + 1] < arr[i] ? right[i + 1] + 1 : 0);
//        }
//
//        int ans = 0;
//        for (int i = 0; i < n; ++i) {
//            if (left[i] > 0 && right[i] > 0) {
//                ans = max(ans, left[i] + right[i] + 1);
//            }
//        }
//        return ans;
//    }
//};

//2038.如果相邻两个颜色均相同则删除当前颜色

//总共有 n 个颜色片段排成一列，每个颜色片段要么是 'A' 要么是 'B' 。给你一个长度为 n 的字符串 colors ，其中 colors[i] 表示第 i 个颜色片段的颜色。
//Alice 和 Bob 在玩一个游戏，他们 轮流 从这个字符串中删除颜色。Alice 先手 。
//如果一个颜色片段为 'A' 且 相邻两个颜色 都是颜色 'A' ，那么 Alice 可以删除该颜色片段。Alice 不可以 删除任何颜色 'B' 片段。
//如果一个颜色片段为 'B' 且 相邻两个颜色 都是颜色 'B' ，那么 Bob 可以删除该颜色片段。Bob 不可以 删除任何颜色 'A' 片段。
//Alice 和 Bob 不能 从字符串两端删除颜色片段。
//如果其中一人无法继续操作，则该玩家 输 掉游戏且另一玩家 获胜 。
//假设 Alice 和 Bob 都采用最优策略，如果 Alice 获胜，请返回 true，否则 Bob 获胜，返回 false。

//class Solution {
//public:
//    bool winnerOfGame(string colors) {
//        int n = colors.size();
//        int ans1 = 0, ans2 = 0, i = 0, start;
//        while (i < n) {
//            start = i;
//            i++;
//            while (i < n && colors[i] == colors[i - 1])
//                i++;
//            int len = i - start;
//            if (len < 3)
//                continue;
//            if (colors[start] == 'A') {
//                ans1 += len - 2;
//            }
//            else
//                ans2 += len - 2;
//        }
//        return ans1 > ans2;
//    }
//};

//2900.最长相邻不相等子序列 I

//给定一个字符串数组 words ，和一个 二进制 数组 groups ，两个数组长度都是 n 。
//如果 words 的一个 子序列 是交替的，那么对于序列中的任意两个连续字符串，它们在 groups 中相同索引的对应元素是 不同 的（也就是说，不能有连续的 0 或 1），
//你需要从 words 中选出 最长交替子序列。
//返回选出的子序列。如果有多个答案，返回 任意 一个。
//注意：words 中的元素是不同的 。

//class Solution {
//public:
//    vector<string> getLongestSubsequence(vector<string>& words, vector<int>& groups) {
//        vector<string> ans;
//        int n = groups.size();
//        for (int i = 0; i < n; i++) {
//            if (i == n - 1 || groups[i] != groups[i + 1]) {
//                ans.push_back(words[i]);
//            }
//        }
//        return ans;
//    }
//};

//1759.统计同质子字符串的数目

//给你一个字符串 s ，返回 s 中 同质子字符串 的数目。由于答案可能很大，只需返回对 109 + 7 取余 后的结果。
//同质字符串 的定义为：如果一个字符串中的所有字符都相同，那么该字符串就是同质字符串。
//子字符串 是字符串中的一个连续字符序列。

//class Solution {
//public:
//    int countHomogenous(string s) {
//        int n = s.size(), cnt = 1;
//        long long ans = 1;
//        for (int i = 1; i < n; i++) {
//            if (s[i] == s[i - 1]) {
//                cnt++;
//            }
//            else {
//                cnt = 1;
//            }
//            ans += cnt;
//        }
//        return ans % 1'000'000'007;
//    }
//};

//3011.判断一个数组是否可以变为有序

//给你一个下标从 0 开始且全是 正 整数的数组 nums 。
//一次 操作 中，如果两个 相邻 元素在二进制下 设置位 的数目 相同 ，那么你可以将这两个元素交换。你可以执行这个操作 任意次 （也可以 0 次）。
//如果你可以使数组变为非降序，请你返回 true ，否则返回 false

// class Solution {
// public:
//     bool canSortArray(vector<int>& nums) {
//         for (int i = 0, n = nums.size(); i < n;) {
//             int start = i;
//             int ones = popcount(static_cast<unsigned>(nums[i++])); //__builtin_popcount效率 == popcount
//             while (i < n && popcount(static_cast<unsigned>(nums[i])) == ones) {
//                 i++;
//             }
//             sort(nums.begin() + start, nums.begin() + i);
//         }
//         return ranges::is_sorted(nums);
//     }
// };
//
//class Solution {
//public:
//    bool canSortArray(vector<int>& nums) {
//        int n = nums.size();
//        int pre_max = 0;
//        for (int i = 0; i < n;) {
//            int mx = 0;
//            int ones = __builtin_popcount(nums[i]);
//            while (i < n && __builtin_popcount(nums[i]) == ones) {
//                if (nums[i] < pre_max) {
//                    return false;
//                }
//                mx = max(mx, nums[i++]);
//            }
//            pre_max = mx;
//        }
//        return true;
//    }
//};

//1578.使绳子变成彩色的最短时间

//Alice 把 n 个气球排列在一根绳子上。给你一个下标从 0 开始的字符串 colors ，其中 colors[i] 是第 i 个气球的颜色。
//Alice 想要把绳子装扮成 五颜六色的 ，且她不希望两个连续的气球涂着相同的颜色，所以她喊来 Bob 帮忙。Bob 可以从绳子上移除一些气球使绳子变成 彩色 。
//给你一个 下标从 0 开始 的整数数组 neededTime ，其中 neededTime[i] 是 Bob 从绳子上移除第 i 个气球需要的时间（以秒为单位）。
//返回 Bob 使绳子变成 彩色 需要的 最少时间 。

//class Solution {
//public:
//    int minCost(string colors, vector<int>& neededTime) {
//        int i = 0, n = colors.size(), ans = 0, maxt{}, sum{};
//        char c{};
//        while (i < n) {
//            c = colors[i];
//            maxt = 0;
//            sum = 0;
//            while (i < n && colors[i] == c) {
//                maxt = max(maxt, neededTime[i]);
//                sum += neededTime[i];
//                i++;
//            }
//            ans += sum - maxt;
//        }
//        return ans;
//    }
//};

//1839.所有元音按顺序排布的最长子字符串

//当一个字符串满足如下条件时，我们称它是 美丽的 ：
//所有 5 个英文元音字母（'a' ，'e' ，'i' ，'o' ，'u'）都必须 至少 出现一次。
//这些元音字母的顺序都必须按照 字典序 升序排布（也就是说所有的 'a' 都在 'e' 前面，所有的 'e' 都在 'i' 前面，以此类推）
//比方说，字符串 "aeiou" 和 "aaaaaaeiiiioou" 都是 美丽的 ，但是 "uaeio" ，"aeoiu" 和 "aaaeeeooo" 不是美丽的 。
//给你一个只包含英文元音字母的字符串 word ，请你返回 word 中 最长美丽子字符串的长度 。如果不存在这样的子字符串，请返回 0 。
//子字符串 是字符串中一个连续的字符序列。

//class Solution {
//public:
//    int longestBeautifulSubstring(string word) {
//        int n = word.size();
//        if (n < 5) {
//            return 0;
//        }
//        int ans = 0, i = 0, index{}, type{};
//        while (i < n) {
//            while (i < n && word[i] != 'a') {
//                i++;
//            }
//            index = i;
//            i++;
//            type = 1;
//            while (i < n && word[i - 1] <= word[i]) {
//                if (word[i - 1] != word[i]) {
//                    type++;
//                }
//                i++;
//            }
//            if (type == 5) {
//                ans = max(ans, i - index);
//            }
//        }
//        return ans;
//    }
//};

//2765.最长交替子数组

//给你一个下标从 0 开始的整数数组 nums 。如果 nums 中长度为 m 的子数组 s 满足以下条件，我们称它是一个 交替子数组 ：
//m 大于 1 。
//s1 = s0 + 1 。
//下标从 0 开始的子数组 s 与数组[s0, s1, s0, s1, ..., s(m - 1) % 2] 一样。也就是说，s1 - s0 = 1 ，s2 - s1 = -1 ，s3 - s2 = 1 ，s4 - s3 = -1 ，以此类推，直到 s[m - 1] - s[m - 2] = (-1)m 。
//请你返回 nums 中所有 交替 子数组中，最长的长度，如果不存在交替子数组，请你返回 - 1 。
//子数组是一个数组中一段连续 非空 的元素序列。

//class Solution {
//public:
//    int alternatingSubarray(vector<int>& nums) {
//        int ans = -1, i = 0, n = nums.size(), index{};
//        while (i < n - 1) {
//            if (nums[i + 1] - nums[i] != 1) {
//                i++;
//                continue;
//            }
//            index = i;
//            i += 2;
//            while (i < n && nums[i] == nums[i - 2]) {
//                i++;
//            }
//            ans = max(ans, i - index);
//            i--;
//        }
//        return ans;
//    }
//};

//3255.长度为 K 的子数组的能量值 II

//给你一个长度为 n 的整数数组 nums 和一个正整数 k 。
//一个数组的 能量值 定义为：
//如果 所有 元素都是依次 连续（即 nums[i] + 1 = nums[i + 1]，i < n）且 上升 的，那么能量值为 最大 的元素。
//否则为 - 1 。
//你需要求出 nums 中所有长度为 k 的 子数组 的能量值。
//请你返回一个长度为 n - k + 1 的整数数组 results ，其中 results[i] 是子数组 nums[i..(i + k - 1)] 的能量值。

//class Solution {
//public:
//    vector<int> resultsArray(vector<int>& nums, int k) {
//        int n = nums.size(), cnt = 0;
//        vector<int> ans(n - k + 1, -1);
//        for (int i = 0; i < n; i++) {
//            cnt = i == 0 || nums[i] == nums[i - 1] + 1 ? cnt + 1 : 1;
//            if (cnt >= k) {
//                ans[i - k + 1] = nums[i];
//            }
//        }
//        return ans;
//    }
//};

//3350.检测相邻递增子数组 II 

//给你一个由 n 个整数组成的数组 nums ，请你找出 k 的 最大值，使得存在 两个 相邻 且长度为 k 的 严格递增 子数组。
//具体来说，需要检查是否存在从下标 a 和 b(a < b) 开始的 两个 子数组，并满足下述全部条件：
//这两个子数组 nums[a..a + k - 1] 和 nums[b..b + k - 1] 都是 严格递增 的。
//这两个子数组必须是 相邻的，即 b = a + k。
//返回 k 的 最大可能 值。
//子数组 是数组中的一个连续 非空 的元素序列

//class Solution {
//public:
//    int maxIncreasingSubarrays(vector<int>& nums) {
//        int ans = 0, pre_cnt = 0, cnt = 0;
//        for (int i = 0; i < nums.size(); i++) {
//            cnt++;
//            if (i == nums.size() - 1 || nums[i] >= nums[i + 1]) {
//                ans = max({ ans, cnt / 2, min(pre_cnt, cnt) });
//                pre_cnt = cnt;
//                cnt = 0;
//            }
//        }
//        return ans;
//    }
//};

//3105.最长的严格递增或递减子数组

//给你一个整数数组 nums 。
//返回数组 nums 中 严格递增 或 严格递减 的最长非空子数组的长度。

//class Solution {
//public:
//    int longestMonotonicSubarray(vector<int>& nums) {
//        int n = nums.size(), i = 0, ans = 1, index{};
//        while (i < n - 1) {
//            if (nums[i] == nums[i + 1]) {
//                i++;
//                continue;
//            }
//            index = i;
//            bool b = nums[i + 1] > nums[i];
//            i += 2;
//            while (i < n && nums[i] != nums[i - 1] && (nums[i] > nums[i - 1]) == b) {
//                i++;
//            }
//            ans = max(ans, i - index);
//            i--;
//        }
//        return ans;
//    }
//};

//135.分发糖果

//n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
//你需要按照以下要求，给这些孩子分发糖果：
//每个孩子至少分配到 1 个糖果。
//相邻两个孩子中，评分更高的那个会获得更多的糖果。
//请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

//class Solution {
//public:
//    int candy(vector<int>& ratings) {
//        int n = ratings.size();
//        int ans = n;
//        for (int i = 0; i < n; i++) {
//            int start = i > 0 && ratings[i - 1] < ratings[i] ? i - 1 : i;
//            while (i + 1 < n && ratings[i] < ratings[i + 1]) {
//                i++;
//            }
//            int top = i;
//
//
//            while (i + 1 < n && ratings[i] > ratings[i + 1]) {
//                i++;
//            }
//            int inc = top - start;
//            int dec = i - top;
//            ans += (inc * (inc - 1) + dec * (dec - 1)) / 2 + max(inc, dec);
//        }
//        return ans;
//    }
//};

//838.推多米诺

//n 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。
//每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。
//如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡， 该骨牌仍然保持不变。
//就这个问题而言，我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。
//给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态，其中：
//dominoes[i] = 'L'，表示第 i 张多米诺骨牌被推向左侧，
//dominoes[i] = 'R'，表示第 i 张多米诺骨牌被推向右侧，
//dominoes[i] = '.'，表示没有推动第 i 张多米诺骨牌。
//返回表示最终状态的字符串。

//class Solution {
//public:
//    string pushDominoes(string s) {
//        int n = s.size();
//        int pre = -1;
//        for (int i = 0; i <= n; i++) {
//            char ch = i < n ? s[i] : 'R';
//            if (ch == '.') {
//                continue;
//            }
//            if (ch == (pre < 0 ? 'L' : s[pre])) {
//                fill(s.begin() + pre + 1, s.begin() + i, ch);
//            }
//            else if (ch == 'L') {
//                fill(s.begin() + pre + 1, s.begin() + (pre + i + 1) / 2, 'R');
//                fill(s.begin() + (pre + i) / 2 + 1, s.begin() + i, 'L');
//            }
//            pre = i;
//        }
//        return s;
//    }
//};

//467.环绕字符串中唯一的子字符串

//定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的：
//"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
//给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。

//class Solution {
//public:
//    int findSubstringInWraproundString(string p) {
//        vector<int> dp(26);
//        int k = 0;
//        for (int i = 0; i < p.length(); ++i) {
//            if (i && (p[i] - p[i - 1] + 26) % 26 == 1) {
//                ++k;
//            }
//            else {
//                k = 1;
//            }
//            dp[p[i] - 'a'] = max(dp[p[i] - 'a'], k);
//        }
//        return accumulate(dp.begin(), dp.end(), 0);
//    }
//};

//3499.操作后最大活跃区段数 I 

//给你一个长度为 n 的二进制字符串 s，其中：
//'1' 表示一个 活跃 区段。
//'0' 表示一个 非活跃 区段。
//你可以执行 最多一次操作 来最大化 s 中的活跃区段数量。在一次操作中，你可以：
//将一个被 '0' 包围的连续 '1' 区块转换为全 '0'。
//然后，将一个被 '1' 包围的连续 '0' 区块转换为全 '1'。
//返回在执行最优操作后，s 中的 最大 活跃区段数。
//注意：处理时需要在 s 的两侧加上 '1' ，即 t = '1' + s + '1'。这些加上的 '1' 不会影响最终的计数。

//class Solution {
//public:
//    int maxActiveSectionsAfterTrade(string s) {
//        int total1 = 0, mx = 0, pre0 = INT_MIN, cnt = 0;
//        for (int i = 0; i < s.size(); i++) {
//            cnt++;
//            if (i == s.size() - 1 || s[i] != s[i + 1]) {
//                if (s[i] == '1') {
//                    total1 += cnt;
//                }
//                else {
//                    mx = max(mx, pre0 + cnt);
//                    pre0 = cnt;
//                }
//                cnt = 0;
//            }
//        }
//        return total1 + mx;
//    }
//};

//413.等差数列划分

//如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
//例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和[3, -1, -5, -9] 都是等差数列。
//给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
//子数组 是数组中的一个连续序列。

//class Solution {
//public:
//    int numberOfArithmeticSlices(vector<int>& nums) {
//        int ans = 0, n = nums.size();
//        if (n < 3) {
//            return ans;
//        }
//        for (int l = 0, r = 1; r < n; r++) {
//            int dis = nums[r] - nums[r - 1];
//            while (r + 1 < n && dis + nums[r] == nums[r + 1]) {
//                r++;
//            }
//            if (l + 1 < r) {
//                ans += (r - l - 1) * (r - l) / 2;
//            }
//            l = r;
//        }
//        return ans;
//    }
//};

//2948.交换得到字典序最小的数组

//给你一个下标从 0 开始的 正整数 数组 nums 和一个 正整数 limit 。
//在一次操作中，你可以选择任意两个下标 i 和 j，如果 满足 | nums[i] - nums[j]| <= limit ，则交换 nums[i] 和 nums[j] 。
//返回执行任意次操作后能得到的 字典序最小的数组 。
//如果在数组 a 和数组 b 第一个不同的位置上，数组 a 中的对应元素比数组 b 中的对应元素的字典序更小，则认为数组 a 就比数组 b 字典序更小。
//例如，数组[2, 10, 3] 比数组[10, 2, 3] 字典序更小，下标 0 处是两个数组第一个不同的位置，且 2 < 10 。

//class Solution {
//public:
//    vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
//        int n = nums.size();
//        vector<int> ids(n);
//        iota(ids.begin(), ids.end(), 0); // 为容器 ids 中的元素赋予从 0 开始的连续递增的整数值
//        sort(ids.begin(), ids.end(), [&](int i, int j) { return nums[i] < nums[j]; });
//
//        vector<int> ans(n);
//        for (int i = 0; i < n;) {
//            int st = i;
//            for (i++; i < n && nums[ids[i]] - nums[ids[i - 1]] <= limit; i++);
//            vector<int> subIds(ids.begin() + st, ids.begin() + i);
//            ranges::sort(subIds);
//            for (int j = 0; j < subIds.size(); j++) {
//                ans[subIds[j]] = nums[ids[st + j]];
//            }
//        }
//        return ans;
//    }
//};

//2593.标记所有元素后数组的分数

//给你一个数组 nums ，它包含若干正整数。
//一开始分数 score = 0 ，请你按照下面算法求出最后分数：
//从数组中选择最小且没有被标记的整数。如果有相等元素，选择下标最小的一个。
//将选中的整数加到 score 中。
//标记 被选中元素，如果有相邻元素，则同时标记 与它相邻的两个元素 。
//重复此过程直到数组中所有元素都被标记。
//请你返回执行上述算法后最后的分数。

//class Solution {
//public:
//    long long findScore(vector<int>& nums) {
//        long long ans = 0;
//        for (int i = 0, n = nums.size(); i < n; i += 2) {
//            int start = i;
//            while (i + 1 < n && nums[i] > nums[i + 1]) {
//                i++;
//            }
//            for (int j = i; j >= start; j -= 2) {
//                ans += nums[j];
//            }
//        }
//        return ans;
//    }
//};

//3640.三段式数组 II

//给你一个长度为 n 的整数数组 nums。
//三段式子数组 是一个连续子数组 nums[l...r]（满足 0 <= l < r < n），并且存在下标 l < p < q < r，使得：
//nums[l...p] 严格 递增，nums[p...q] 严格 递减，nums[q...r] 严格 递增。
//请你从数组 nums 的所有三段式子数组中找出和最大的那个，并返回其 最大 和。

//class Solution {
//public:
//    long long maxSumTrionic(vector<int>& nums) {
//        int n = nums.size();
//        long long ans = LLONG_MIN;
//        for (int i = 0; i < n;) {
//            // 第一段
//            int start = i;
//            for (i++; i < n && nums[i - 1] < nums[i]; i++);
//            if (i == start + 1) { // 第一段至少要有两个数
//                continue;
//            }
//
//            // 第二段
//            int peak = i - 1;
//            long long res = nums[peak - 1] + nums[peak]; // 第一段的最后两个数必选
//            for (; i < n && nums[i - 1] > nums[i]; i++) {
//                res += nums[i]; // 第二段的所有元素必选
//            }
//            if (i == peak + 1 || i == n || nums[i - 1] == nums[i]) { // 第二段至少要有两个数，第三段至少要有两个数
//                continue;
//            }
//
//            // 第三段
//            int bottom = i - 1;
//            res += nums[i]; // 第三段的前两个数必选（第一个数在上面的循环中加了）
//            // 从第三段的第三个数往右，计算最大元素和
//            long long max_s = 0, s = 0;
//            for (i++; i < n && nums[i - 1] < nums[i]; i++) {
//                s += nums[i];
//                max_s = max(max_s, s);
//            }
//            res += max_s;
//
//            // 从第一段的倒数第三个数往左，计算最大元素和
//            max_s = 0; s = 0;
//            for (int j = peak - 2; j >= start; j--) {
//                s += nums[j];
//                max_s = max(max_s, s);
//            }
//            res += max_s;
//            ans = max(ans, res);
//
//            i = bottom; // 第三段的起点也是下一个极大三段式子数组的第一段的起点
//        }
//        return ans;
//    }
//};